Parcours dans un graphe (2) - Corrigé

Énoncé

Voici un graphe.

1. Peut-on parcourir une fois et une seule chacune de ses arêtes ?

2. Si cela est possible, peut-on partir de n'importe quel sommet ?

3. Proposer une chaîne eulérienne dans ce graphe.

Solution 

1. Le sommet E est de degré 1, les sommets A et C sont de degré 2, le sommet D est de degré 3 et le sommet B est de degré 4. Il y a donc exactement deux sommets de degré impair (qui sont D et E). D'après le théorème d'Euler, il est donc possible de trouver un tel parcours, appelé chaîne eulérienne.

2. D'après le théorème d'Euler, les sommets de degré impair s'ils existent sont forcément le départ et/ou l'arrivée d'une chaîne d'Euler. Donc les seuls points de départ possibles sont D et E.

3. Une chaine eulérienne possible est : E-B-D-C-B-A-D.
Autre possibilité : E-B-A-D-C-B-D